Important processing types in digital signal processing include fast Fourier transform (hereinafter referred to as “FFT”) processing. Further, as a technology of compensating for waveform distortion in signal transmission in wireless communication and wired communication, for example, a frequency domain equalization (FDE) technology is known. In frequency domain equalization, signal data in a time domain are first transformed into data in a frequency domain by a fast Fourier transform, and next, filter processing for equalization is performed. Then, data after the filter processing are retransformed into signal data in a time domain by inverse fast Fourier transform (hereinafter referred to as “IFFT”) so that waveform distortion in the original signal in a time domain is compensated for. FFT and IFFT are hereinafter referred to as “FFT/IFFT” when they are not distinguished.
In general, “butterfly calculation” is used in FFT/IFFT processing. An FFT device using butterfly calculation is described in, for example, PTL 1. PTL 1 also describes “twiddle multiplication” to be described later, that is, multiplication using a twiddle coefficient.
As an efficient FFT/IFFT processing method, for example, butterfly calculation by Cooley-Tukey described in NPL 1 is well known. However, the FFT/IFFT processing method by Cooley-Tukey has a large number of points and therefore a circuit for providing the processing method is complex. Consequently, FFT/IFFT processing is performed by breaking down an FFT/IFFT into two smaller-sized FFT/IFFTs by use of, for example, a prime factor method described in NPL 2.
FIG. 7 illustrates, for example, a data flow 500 of a 64-point FFT broken down into sets of two-stage radix-8 butterfly processing by use of the prime factor method. The data flow 500 includes data sorting processing 501, a total of 16 sets of radix-8 butterfly calculation processing composed of butterfly calculation processing 502 and 503, and twiddle multiplication processing 504.
In the data flow illustrated in FIG. 7, input time-domain data x(n) (n=0, 1, . . . , 63) are Fourier-transformed into a frequency-domain signal X(k) (k=0, 1, . . . , 63) by FFT processing. In the example illustrated in FIG. 7, illustration of part of the data flow is omitted. Note that a basic configuration of the data flow illustrated in FIG. 7 is the same for IFFT processing.
When a number of points of an FFT is large, an enormous circuit scale is required in order to provide the entire data flow illustrated in FIG. 7 by a circuit. Consequently, when a number of points of an FFT is large, a method of providing the entire FFT processing by repetitive use of a circuit providing part of the processing of the data flow, depending on required processing performance, is common.
For example, in the data flow illustrated in FIG. 7, when an FFT device performing FFT processing on eight pieces of data in parallel (hereinafter simply referred to as “in 8-data-parallel”) is created as a physical circuit, 64-point FFT processing can be provided by a total of eight sets of repetitive processing.
The eight sets of repetitive processing represent successively performing processing corresponding to each of partial data flows 505a to 505h performed on eight pieces of data, and are specifically performed as follows. That is, processing corresponding to the partial data flow 505a is performed in a first round, processing corresponding to the partial data flow 505b is performed in a second round, and processing corresponding to the partial data flow 505c (not illustrated) is performed in a third round. Thereafter, processing is successively performed in a similar manner up to processing corresponding to the partial data flow 505h in an eighth round. The processing described above provides the 64-point FFT processing.
In butterfly calculation, data arranged in sequential order are read in an order conforming to a predetermined rule, and processed. Thus, data sorting is required in butterfly calculation, and a random access memory (RAM) is used for the purpose. An FFT device performing data sorting using a RAM in butterfly calculation is described in, for example, PTL 2.
Further, as for an FFT calculation device with a reduced memory usage amount, an acceleration technology by parallel processing of butterfly calculation is described in, for example, PTL 3.
Meanwhile, in FFT, it is assumed that data identical with a range of an extracted input signal being a processing target, that is, a set of consecutive input data (hereinafter referred to as “processing block”) are periodically repeated. However, an actual signal is not necessarily a periodic signal, and therefore there is a problem that calculation distortion occurs near both ends of a processing block after FFT.
As a technology solving the problem, for example, an “overlap method” may be cited. In the overlap method, adjacent processing blocks are overlapped by a predetermined number of pieces of data, and FFT processing is performed. Data after FFT processing undergo filter processing and then retransformed into a time-domain signal by IFFT processing. Then, partial data at both ends where calculation distortion occurs in an overlapped processing block are removed. A part of processing block data to be removed is hereinafter referred to as “removal part” and a part not removed but output is referred to as “output part.”
The overlap method is also applied to FDE (refer to, for example, PTL 4 and 5). An overlap FDE method in which the overlap method is applied to FDE will be described. FIG. 8 is a block diagram illustrating a configuration example of a digital filter circuit 700 by the overlap FDE method. The digital filter circuit 700 is a frequency-domain filter circuit performing filter processing in a frequency domain. Specifically, a time-domain signal input as input data is transformed into frequency-domain data by FFT and subsequently undergoes filter processing. Then, the signal after the filter processing is retransformed into a time-domain signal by IFFT and output as an output signal.
The digital filter circuit 700 includes an overlap addition circuit 710, an FFT circuit 711, a filter calculation circuit 712, an IFFT circuit 713, and an overlap removal circuit 714.
The overlap addition circuit 710 successively generates a block composed of N pieces of data (where N is a positive integer) from input data which is a time-domain input signal, and outputs the block to the FFT circuit 711. At this time, the overlap addition circuit 710 causes each block to have M pieces of data (where M is a positive integer) overlapped with an immediately preceding block. The number of pieces of data to be overlapped M is hereinafter referred to as “overlap amount.” Further, an overlapped part in each block is referred to as “overlap part.”
An overlap amount M may be a predetermined fixed value. In that case, the overlap addition circuit 710 and the overlap removal circuit 714 are configured in accordance with a value of the overlap value M. Alternatively, for example, the overlap addition circuit 710 and the overlap removal circuit 714 may refer to a set value of an overlap amount M given by an upper circuit (not illustrated) such as a central processing unit (CPU) and set the value when in operation. Note that the overlap addition circuit 710 may be configured by, for example, a dual-port memory.
The FFT circuit 711 performs FFT on a time-domain input signal with M pieces of data overlapped thereon, being output from the overlap addition circuit 710, transforms the signal into a frequency-domain signal, and outputs the signal to the filter calculation circuit 712.
The filter calculation circuit 712 performs filter processing on a frequency-domain signal transformed by the FFT circuit 711, and outputs the signal to the IFFT circuit 713. For example, when the digital filter circuit 700 performs processing of equalizing signal distortion in a communication channel, the filter calculation circuit 712 may be configured with a complex number multiplier.
The IFFT circuit 713 performs IFFT on a frequency-domain signal after filter processing, output from the filter calculation circuit 712, to retransform the signal into a time-domain signal, and outputs the signal to the overlap removal circuit 714.
The overlap removal circuit 714 removes a total of M pieces of data from both ends of each block composed of N pieces of data which is a time-domain signal retransformed by the IFFT circuit 713. At this time, a part to be removed is the aforementioned “removal part” and the amount of the data is equal to the overlap amount M. Then, the overlap removal circuit 714 outputs data in an “output part” included in an overlap part and data in a middle part of a block not overlapped as output data.
An operation of the digital filter circuit 700 illustrated in FIG. 8 will be described below with reference to FIG. 9. FIG. 9 is an operation diagram illustrating an operation example of the digital filter circuit illustrated in FIG. 8. In the description below, processing steps (1) to (5) respectively correspond to processing steps (1) to (5) in FIG. 9.
(1) Overlap Addition Processing
The overlap addition circuit 710 successively generates a block composed of N pieces of data (where N is a positive integer) from input data which is a time domain input signal. At this time, the overlap addition circuit 710 causes the block to have M pieces of data overlapped with an immediately preceding block.
When input data are denoted asx(i)(i=0,1, . . . ),a block composed of N pieces of data is expressed asx(j)(j=m(N−M)−N to m(N−M)−1, where m is a positive integer).Note that N denotes an FFT block size and M denotes an overlap amount.(2) FFT Processing
The FFT circuit 711 performs FFT on a block composed of time-domain signal data, and transforms the block into a block composed of frequency-domain signal data.
Again, when a block composed of N pieces of time-domain signal data is denoted asx(n)(n=0,1, . . . ,N−1),a block in a frequency domain after the FFT processing is given byX(k)(k=0,1, . . . ,N−1).(3) Frequency Domain Filter Processing
The filter calculation circuit 712 performs filter processing on each piece of signal data in a frequency domain, composing a block after FFT processing.
A block after the filter processing corresponding to a block X(k) before the filter processing is given byX′(k)=H(k)·X(k)(k=0,1, . . . ,N−1).Note that H(k) denotes a filter coefficient.(4) IFFT Processing
The IFFT circuit 713 performs IFFT on a block composed of frequency-domain signal data after filter processing to retransform the block into a block composed of time-domain signal data.
A block after the IFFT processing corresponding to a block X′(k) before the IFFT processing is given byy(n)(n=0,1, . . . ,N−1).(5) Overlap Removal Processing
From the block y(n) composed of N pieces of signal data after the IFFT processing, the overlap removal circuit 714 extracts a middle part by removing M/2 pieces of overlapped data from the start and the end of the block, respectively, that is, data in a removal part.
Thus, data in the removal part are removed, and a sequence of (N−M) pieces of signal data composed of an output part included in an overlap part of the block y(n) and the middle part not overlapped, expressed asy′(j)(j=M/2 to (N−1)−M/2),is generated.
There exists a digital filter circuit using overlap processing for general filter processing, not being limited to FDE and the like (refer to, for example, PTL 6). The digital filter circuit in PTL 6 also performs overlap addition processing, FFT processing, frequency domain filter processing, IFFT processing, and overlap removal processing.
Meanwhile, an overlap amount required in a filter using overlap processing is determined in accordance with an impulse response length of executed filter processing. Additionally, a size of an FFT processing block needs to be greater than the required overlap amount. Consequently, a size of the FFT processing block is determined in accordance with an impulse response length of the filter processing.
There is a technology of decreasing a hardware amount of a processing device performing FFT on blocks with varying sizes (refer to, for example, PTL 7). An orthogonal transformation processor in PTL 7 determines a memory size adapting to a length of an FFT vector (corresponding to “processing block”), disables an unnecessary circuit block, and operates hardware in a time-division manner.